1. Technical Field
Aspects of this document relate generally to the fields of data compression and decompression.
2. Background Art
Existing specialized content addressable memory (CAM)-based architecture has traditionally been used for searching for optimal matches among historical data in data compression engines. This architecture has allowed every possible match to be tracked to find the longest match; however, one drawback of such a system is that it doesn't scale well with larger history sizes and causes routing problems, particularly in FPGA's.
The general concept of a hash-based compression architecture is also known in software compression engines as well as hash-based compression hardware. A hashing algorithm typically looks only at one potential match at a time and has to evaluate several potential matches to determine which potential match is the best one. To improve the speed of this process the search ends when a “good enough” match is found. This results in variable throughput based on the number of potential matches searched and the data being compressed.
The complexity of Lempel-Ziv (LZ) compression lies in searching for repeated strings in a stream of data. This search has traditionally been time consuming in software development and resource-intensive in terms of hardware needed. U.S. Pat. No. 8,046,532 provides one such example of CAM based data compression, the content of which is incorporated herein by reference in its entirety.